﻿#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
//169. 多数元素
//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。
//示例 1：
//输入：nums = [3, 2, 3]
//输出：3
//示例 2：
//
//输入：nums = [2, 2, 1, 1, 1, 2, 2]
//输出：2


//摩尔投票法
int majorityElement(int* nums, int numsSize) {
	int winner = nums[0];//假设winner是第一个元素
	int count = 1;
	for (int i = 1; i < numsSize; i++)
	{
		if (winner == nums[i])
		{
			count++;
		}
		else
		{
			count--;
		}
		//当投票为零时说明winner没人支持了需要变为当前元素同时让其票数为1接着与下一个元素碰撞
		if (count == 0)
		{
			winner = nums[i];
			count = 1;
		}
	}
	return winner;
}